package merisis.experiments.gcs;

public class GCSearch7 extends AbstractGuessComplemetSearch {

	public long searchAlgoritm(long start, long end, long key) {

		long entrance = (start + end) >> 1;
		//entrance *= 3;

		long top = end;
		long btm = start;
		long topVal = 0;
		long btmVal = 0;
		long winlen;
		double slope0;
		long entranceVal = access(entrance);

		if (key < entranceVal) {

			top = entrance;
			topVal = entranceVal;

			// Assume that the key is at the middle.
			winlen = top - btm;
			slope0 = ((double)(entranceVal - key)) / (winlen >> 1);
			if (GCSEInstrument.DEBUG) {
				System.out.println("slope: " + slope0);
			}

		} else if (key > entranceVal) {

			btm = entrance;
			btmVal = entranceVal;

			// Assume that the key is at the middle.
			winlen = top - btm;
			slope0 = ((double)(key - entranceVal)) / (winlen >> 1);
			if (GCSEInstrument.DEBUG) {
				System.out.println("slope: " + slope0);
			}
		} else {
			return entrance;
		}
		
		recodeGuess(btm, top, btmVal, topVal, entrance, slope0);

		boolean hit = true;

		while (btm <= top) {

			long mid; // conservative
			double slope;
			long decision;

			// long lhsum = btm + top;
			winlen = top - btm;
			mid = (btm + top) >> 1;
			if (hit && mid != btm) {
				if (topVal > 0) {
					//
					long winweight = topVal - btmVal;
					slope = ((double)winweight) / winlen;
					long b2 = top - (long) (((double) (topVal - key)) / slope);
					if (b2 < btm) {
						b2 = btm;
					}
					decision = b2;

					slope0 = slope;
					//
				} else {

					// Because the top boundary is not determined, use the
					// previous slope.
					slope = slope0;

					decision = btm + (long) (((double) (key - btmVal)) / slope);
					if (decision > top) {
						decision = top;
					}

				}
				recodeGuess(btm, top, btmVal, topVal, decision, slope);
			} else {
				decision = mid;
				recodeFold(btm, top, btmVal, topVal);
			}

			long jumpVal;
			jumpVal = access(decision);

			if (key > jumpVal) {

				btm = decision + 1;
				btmVal = jumpVal;

				if (hit) {
					if ((decision - btm) >= (top - decision)) {
						// +------c--g-k-+
					} else {
						// +--g-k-c--k---+
						hit = false; // the stake is lost.
					}
				} else {
					hit = true; // The trust to guess is recovered
				}

			} else if (key < jumpVal) {

				top = decision - 1;
				topVal = jumpVal;
				if (hit) {
					if ((decision - btm) >= (top - decision)) {
						// +-k----c-k-g---+
						hit = false; // the stake is lost.
					} else {
						// +-k-g---c------+
					}
				} else {
					hit = true; // The trust to guess is recovered
				}
			} else
				return decision; // key found
		}

		return -(btm + 1); // key not found.
	}

	public void recodeGuess(long winbtm, long wintop, long winBtmVal,
			long winTopVal, long decision, double slope) {

		if (!GCSEInstrument.DEBUG)
			return;

		System.out.println(String.format(
				"%03d> win{[%d,%d,%d]=(%d,%d,%d)} guess=%d, slope=%.3f",
				instrument.getAccessCount(), winbtm, (wintop + winbtm) >> 1,
				wintop, winBtmVal, (winBtmVal + winTopVal) >> 1, winTopVal,
				decision, slope));
	}

	public void recodeFold(long winbtm, long wintop, long winBtmVal,
			long winTopVal) {

		if (!GCSEInstrument.DEBUG)
			return;

		System.out.println(String.format("%03d> win{[%d,%d,%d]=(%d,%d,%d)}",
				instrument.getAccessCount(), winbtm, (wintop + winbtm) >> 1,
				wintop, winBtmVal, (winBtmVal + winTopVal) >> 1, winTopVal));
	}

}
